package com.leetcode.hot100;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: com.leetcode.hot100
 * @Author: lei
 * @CreateTime: 2024-03-13  09:27
 * @Description: 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组是数组中的一个连续部分。
 * @Version: 1.0
 */
public class 最大子数组和_53 {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums));

    }

    private static int maxSubArray(int[] nums) {
        int temp = 0;
        int result = nums[0];
        for (int num : nums) {
            if (temp > 0) {
                temp += num;
            } else {
                temp = num;
            }
            result = Math.max(temp, result);
        }
        return result;
    }

    /**
     * @description: 超时报错
     * @author: lei
     * @date: 2024/3/13 10:31
     * @param: [nums]
     * @return: int
     **/
    public static int maxSubArray01(int[] nums) {
        int result = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int temp = 0;
            for (int j = i; j < nums.length; j++) {
                temp += nums[j];
                if (temp > result) {
                    result = temp;
                }
            }
            if (i < (nums.length - 1) && nums[i] > nums[i + 1]) i += 1;
        }
        return result;
    }
}
